package com.wtgroup.demo.mianshi.算法.排序2305;

import com.wtgroup.demo.common.util.ABTest;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tools;

import java.util.Arrays;
import java.util.Stack;

/**
 * !! 一定不要含枢纽值自身, 否则, 可能死循环
 * (pivot),大,大,大,pivot,pivot
 */
public abstract class QuickSort {

    public static void main(String[] args) {

        testP();

        // Judger.of(() -> {
        //             int[] arr = RandomUtil.randomArray(RandomUtil.randomInt(0, 100), 0, 1000);
        //             // int[] arr = {5, 5, 8, 9, 5};
        //             int[] copy1 = Arrays.copyOf(arr, arr.length);
        //             // new M1().quickSort(copy1);
        //             new M2_3color().quickSort(copy1);
        //             // new M2_Loop().quickSort(copy1);
        //
        //             int[] copy2 = Arrays.copyOf(arr, arr.length);
        //             Arrays.sort(copy2);
        //             return Tools.equals(copy1, copy2);
        //         })
        //         .start().print();

        // Judger.of(() -> {
        //     int[] arr = RandomUtil.randomArray(RandomUtil.randomInt(0, 100_0000), 0, 1000);
        //     int[] copy1 = Arrays.copyOf(arr, arr.length);
        //     int[] copy2 = Arrays.copyOf(arr, arr.length);

        //     long cost1 = Tools.time("递归", () -> {
        //         new M1().quickSort(copy1);
        //     });
        //     long cost2 = Tools.time("循环", () -> {
        //         new M2_Loop().quickSort(copy2);
        //     });

        //     return cost1 > cost2;
        // }).setFailFast(false).setIterCount(100).start().print();

    }

    /**
     * 普通            三色国旗            -
     * 1秒350毫秒  310毫秒  1040
     * ---
     * iter: 10
     * 数据量: 100_0000
     */
    public static void testP() {
        ABTest abTest = new ABTest("普通", "三色国旗");
        M1 m1 = new M1();
        M2_3color m23color = new M2_3color();
        for (int i = 0; i < 10; i++) {
            int[] arr = RandomUtil.randomArray(RandomUtil.randomInt(0, 100_0000), 0, 1000);
            int[] copy1 = Arrays.copyOf(arr, arr.length);
            int[] copy2 = Arrays.copyOf(arr, arr.length);

            abTest.runA(() -> m1.quickSort(copy1));
            abTest.runB(() -> m23color.quickSort(copy2));
        }

        abTest.print();
    }



    public abstract void quickSort(int[] arr);

    static class M2_3color {
        public void quickSort(int[] arr) {
            quickSort0_3color(arr, 0, arr.length - 1);
        }

        void quickSort0_3color(int[] arr, int st, int ed) {
            if (st >= ed) {
                return;
            }
            // 分两部分, 左边<=pivot, 右边>=pivot
            int[] ints = partition_3color(arr, st, ed);
            quickSort0_3color(arr, st, ints[0] - 1);
            quickSort0_3color(arr, ints[1] + 1, ed);
        }

        // 三色国旗方式, 小-中-大, 小-等-大
        int[] partition_3color(int[] arr, int L, int R) {
            // Tools.swap(arr, L + (int) (Math.random() * (R - L + 1)), R);

            // 由于它天然能将等的聚在一起, 最后不需要互换
            int pivot = arr[R];
            // 小的换到前面去; 大的换到后面去, 但换过来的是个什么东东, 不动, 下一轮在观察它
            int left = L, right = R, i = L;
            while (i <= right) {
                if (arr[i] < pivot) {
                    Tools.swap(arr, i, left);
                    left++;
                    i++;
                } else if (arr[i] > pivot) {
                    Tools.swap(arr, i, right);
                    right--;
                    // i 不动
                } else {
                    i++;
                }
            }

            return new int[]{left, right}; // 等区 左右边界
        }

    }

    static class M1 extends QuickSort {
        public void quickSort(int[] arr) {
            quickSort0(arr, 0, arr.length - 1);
        }

        private void quickSort0(int[] arr, int st, int ed) {
            if (st >= ed) {
                return;
            }
            // 分两部分, 左边<=pivot, 右边>=pivot
            int splitIdx = partition(arr, st, ed);
            quickSort0(arr, st, splitIdx - 1);
            quickSort0(arr, splitIdx + 1, ed);
        }

        // 博文，简单易记
        // -: 需要考虑, 最后枢纽位和谁互换, (<, <= 条件是不一样的)
        private int partition(int[] arr, int start, int end) {
            // 从前往后一个方向, 小的往前, 大的往后
            int pivot = arr[start];
            int slot = start + 1; // 小区末尾动态界限, 用于放小值的动态槽位, 一旦发生交换则后移一位
            for (int i = slot; i <= end; i++) {
                if (arr[i] < pivot) {
                    Tools.swap(arr, slot, i);
                    slot++;
                }
            }
            Tools.swap(arr, start, slot - 1);
            return slot - 1;
        }

        /**
         * 《算法v4》 巧妙但复杂点
         * !! 并不好 !!
         * 1. 等于的混在小和大之间, 需要渐进收敛, 才会将等于的聚在一起
         * 2. 也不是太好记
         */
        private int partition_sf(int[] arr, int st, int ed) {
            int pivot = arr[st]; // 0 位置位基准就可以了
            int lt = st; // 跳过第0个
            int rt = ed + 1;
            while (true) {
                while (lt < ed && arr[++lt] <= pivot) {
                }
                while (rt > st && arr[--rt] >= pivot) {
                }
                if (lt < rt) {
                    Tools.swap(arr, lt, rt);
                } else {
                    break;
                }
            }

            // 一定是和 rt 互换, rt <= lt, 和小值互换
            Tools.swap(arr, st, rt);

            return rt;
        }

    }


    /*
     * 递归100%快于循环
     */

    // 循环方式实现
    static class M2_Loop extends QuickSort {
        public void quickSort(int[] arr) {

            Stack<int[]> stack = new Stack<>();
            stack.push(new int[]{0, arr.length - 1});

            while (!stack.isEmpty()) {
                int[] ctx = stack.pop();
                int left = ctx[0], right = ctx[1];
                if (left >= right) {
                    continue;
                }

                int splitIdx = partition(arr, left, right);

                // 左右分支并行调递归了，一次递归一次压栈出栈
                stack.push(new int[]{left, splitIdx - 1});
                stack.push(new int[]{splitIdx + 1, right});
            }

        }

        private int partition(int[] arr, int start, int end) {
            // 从前往后一个方向, 小的往前, 大的往后
            int pivot = arr[start];
            int slot = start + 1; // 小区末尾动态界限, 用于放小值的动态槽位, 一旦发生交换则后移一位
            for (int i = slot; i <= end; i++) {
                if (arr[i] < pivot) {
                    Tools.swap(arr, slot, i);
                    slot++;
                }
            }
            Tools.swap(arr, start, slot - 1);
            return slot - 1;
        }

    }


    // /*
    //  * // 2017年9月24日 下午9:13:50  Nisus
    //  * 快速排序方法(升序) I: 数组, 数组第一个索引值, 数组最后一个索引值
    //  */
    // /*
    //  * 定义两个指针:l++, h--, 以第一个数为基准数key, 从后往前搜索比较, <key, 继续向前 ; 否则, 停止搜索,
    //  * 并将该位置的数"挖出来", 填入arr[l]中, (留下来的坑应该又前往后找到第一个比key大的数填入) 切换到从前往后搜索,
    //  * 遇到第一个>key的数填入arr[h]
    //  */
    // public static void qSort(int[] arr, int start, int end) {

    // 	/* 异常控制 */
    // 	if (start >= end)
    // 		System.err.println("'start' must less than 'end'");

    // 	int l = start; // 初始化指针
    // 	int h = end;
    // 	int key = arr[l];

    // 	while (l < h) {
    // 		while (l < h && arr[h] >= key) { // 开始从后往前搜索
    // 			h--;
    // 		} // *: 含有指针的程序中, 只要前面可能会发生指针变动, 后面一定要紧跟着对指针的判断
    // 		if (l < h) {
    // 			arr[l] = arr[h]; // 挖出来填到前面的坑里
    // 			l++; // 前索引后一位, 减少一次重复比较
    // 		}
    // 		// 立即切换到从前往后搜索
    // 		while (l < h && arr[l] <= key) {
    // 			l++;
    // 		}
    // 		if (l < h) {
    // 			arr[h] = arr[l];
    // 			h--;
    // 		}
    // 	}
    // 	// 循环结束时, l==h
    // 	arr[l] = key;
    // 	// 递归调用//
    // 	if (start < l - 1)
    // 		qSort(arr, start, l - 1);
    // 	if (l + 1 < end)
    // 		qSort(arr, l + 1, end);

    // }


}
